package zhoujian.oj.leetcode;

import java.util.Arrays;

/*
 * There are N children standing in a line. Each child is assigned a rating value.
 * 
 * You are giving candies to these children subjected to the following requirements:
 * 		Each child must have at least one candy.
 * 		Children with a higher rating get more candies than their neighbors.
 * 
 * What is the minimum candies you must give?
 */
public class Candy {

	// worst case: O(n^2)
	public int candyRecuisive(int[] ratings) {
        if (ratings == null) return 0; 
		
		int length = ratings.length;
		
		if (length == 0) {
			return 0;
		}
		
		if (length == 1) {
		    return 1;
		}
		
        int count = 0;
        int[] value = new int[length];
        value[0] = 1;
        for (int i = 1; i < length; i++) {
        	if (ratings[i - 1] < ratings[i] ) {
        		value[i] = value[i - 1] + 1;
        	} else if (ratings[i] == ratings[i - 1]) {
        		value[i] = 1;
        	} else {
        		value[i] = 1;
        		if (value[i - 1] == 1) {
        			value[i - 1] = value[i - 1] + 1;
        			for (int j = i - 1; j > 0; j--) {
        				if (ratings[j - 1] > ratings[j] && value[j - 1] == value[j]) {
        					value[j - 1] = value[j - 1] + 1;
        				} else {
        					break;
        				}
        			}
        		}
        	}
        }
        
        for (int i = 0; i < length; i++) {
        	count += value[i];
        }
        
		return count;
    }
	
	// O(n)
	public int candy(int[] ratings) {
        if (ratings == null) return 0; 
		
		int length = ratings.length;
		
		if (length == 0) {
			return 0;
		}
		
		if (length == 1) {
		    return 1;
		}
		
        int count = 0;
        int[] value = new int[length];
        Arrays.fill(value, 1);
        
        for (int i = 1; i < length; i++) {
        	if (ratings[i - 1] < ratings[i]) {
        		value[i] = value[i - 1] + 1;
        	}
        }
        
        for (int i = length - 1; i > 0; i--) {
        	if (ratings[i - 1] > ratings[i] && value[i - 1] <= value[i]) {
        		value[i - 1] = value[i] + 1;
        	}
        }
        
        for (int i = 0; i < length; i++) {
        	count += value[i];
        }
        
		return count;
    }
	
	public static void main(String[] args) {
		int[] ratings;
		Candy candy = new Candy();
		
		ratings = new int[]{3,2,0,1,5,4};
		assert candy.candy(ratings) == 12;
		
		ratings = new int[]{};
		assert candy.candy(ratings) == 0;
		
		ratings = new int[]{1,2,2,2,1};
		assert candy.candy(ratings) == 7;
		
		ratings = new int[]{1,2,3,3,3};
		assert candy.candy(ratings) == 8;
		
		assert candy.candy(null) == 0;
		
		ratings = new int[]{1,2,5,3,3,1,1};
		assert candy.candy(ratings) == 11;
		
		ratings = new int[]{1,2,5,6,3,1};
		assert candy.candy(ratings) == 13;
	}

}
